<?php
/*
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：

0 <= 节点个数 <= 10000



难度：中等

https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/


*/

require_once '../class/TreeNode.class.php';
$arr1 = [3,4,5,1,2];
$arr2 = [3,4,5,1,2];
$head1 = generateTreeByArray($arr1);
$head2 = generateTreeByArray($arr2);
$obj = new Code_Offer26();
$res = $obj->main($head1, $head2);

class Code_Offer26
{
    public function main($A, $B)
    {
        if ($A == null || $B == null) {
            return false;
        }
        // A的根节点 vs B的根节点，相同的话一次比较他们的子节点
        return $this->isSub($A, $B) || $this->main($A->left, $B) || $this->main($A->right, $B);
    }

    protected function isSub($A, $B)
    {
        // 遍历完B直到null，说明B的全部节点匹配上
        if ($B == null) {
            return true;
        }
        // A中的节点为空，B不为空，不匹配
        if ($A == null) {
            return false;
        }
        // 值不相等也是不匹配的
        if ($A->val != $B->val) {
            return false;
        }
        // 值相等的节点，再比较左右子树
        return $this->isSub($A->left, $B->left) && $this->isSub($A->right, $B->right);
    }
}